package 牛客题霸;

public class 寻找第K大 {

    public static int findKth(int[] a, int n, int k) {
        if(k >= n || a.length <= 0) {
            return -1;
        }
        quickSort(a,0,a.length - 1);
        return a[n - k];
    }

    public static void quickSort(int[] a,int left,int right) {
        if(left >= right || a == null || a.length <= 0) {
            return;
        }
        int base = a[left];
        int low = left;
        int high = a.length - 1;
        while (low != high) {
            while (low < high && a[high] >= base) {
                high--;
            }
            while (low < high && a[low] <= base) {
                low++;
            }
            int temp = a[low];
            a[low] = a[high];
            a[high] = temp;
        }
        a[left] = a[low];
        a[low] = base;
        quickSort(a,left,low - 1);
        quickSort(a,low + 1,right);
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,2,2};
        int kth = findKth(array, 5, 3);
        System.out.println(kth);
    }
}
